using System.Collections.Generic;

namespace PathX.Collection
{
    /// <summary>
    /// Priority queue where same priority items will leave the queue in a FIFO manner
    /// </summary>
    /// <typeparam name="T">The item type</typeparam>
    public partial class PriorityQueueFifo<T> : BinaryHeapBase<PriorityQueueFifo<T>.QueueItemFifo>
    {
        private int _entryIdx;

        /// <summary>
        /// Initializes a new instance of the <see cref="T:Apex.DataStructures.PriorityQueueFifo`1" /> class.
        /// </summary>
        /// <param name="capacity">The capacity.</param>
        /// <param name="type">The type of queue.</param>
        public PriorityQueueFifo(int capacity, QueueType type)
            : base(capacity, type == QueueType.Max ? PriorityQueueFifo<T>.ItemComparerMax.instance : PriorityQueueFifo<T>.ItemComparerMin.instance)
        {
        }

        /// <summary>Enqueues the specified item.</summary>
        /// <param name="item">The item.</param>
        /// <param name="priority">The priority.</param>
        public void Enqueue(T item, int priority) => this.AddInternal(new PriorityQueueFifo<T>.QueueItemFifo(item, priority, this._entryIdx++));

        /// <summary>Dequeues the next item in the queue.</summary>
        /// <returns>The item</returns>
        public T Dequeue() => this.RemoveInternal().item;

        /// <summary>Wraps each item in the queue.</summary>
        public struct QueueItemFifo
        {
            private T _item;
            private int _priority;
            private int _entryOrder;

            /// <summary>
            /// Initializes a new instance of the <see cref="T:Apex.DataStructures.PriorityQueueFifo`1.QueueItemFifo" /> struct.
            /// </summary>
            /// <param name="item">The item.</param>
            /// <param name="priority">The priority.</param>
            /// <param name="entryOrder">The entry order.</param>
            public QueueItemFifo(T item, int priority, int entryOrder)
            {
                this._item = item;
                this._priority = priority;
                this._entryOrder = entryOrder;
            }

            /// <summary>Gets the item.</summary>
            /// <value>The item.</value>
            public T item => this._item;

            /// <summary>Gets the priority.</summary>
            /// <value>The priority.</value>
            public int priority => this._priority;

            /// <summary>Gets the entry order.</summary>
            /// <value>The entry order.</value>
            public int entryOrder => this._entryOrder;
        }

        private class ItemComparerMax : IComparer<PriorityQueueFifo<T>.QueueItemFifo>
        {
            public static readonly IComparer<PriorityQueueFifo<T>.QueueItemFifo> instance = (IComparer<PriorityQueueFifo<T>.QueueItemFifo>)new PriorityQueueFifo<T>.ItemComparerMax();

            public int Compare(PriorityQueueFifo<T>.QueueItemFifo x, PriorityQueueFifo<T>.QueueItemFifo y)
            {
                int num = x.priority.CompareTo(y.priority);
                return num == 0 ? y.entryOrder.CompareTo(x.entryOrder) : num;
            }
        }

        private class ItemComparerMin : IComparer<PriorityQueueFifo<T>.QueueItemFifo>
        {
            public static readonly IComparer<PriorityQueueFifo<T>.QueueItemFifo> instance = (IComparer<PriorityQueueFifo<T>.QueueItemFifo>)new PriorityQueueFifo<T>.ItemComparerMin();

            public int Compare(PriorityQueueFifo<T>.QueueItemFifo x, PriorityQueueFifo<T>.QueueItemFifo y)
            {
                int num = y.priority.CompareTo(x.priority);
                return num == 0 ? y.entryOrder.CompareTo(x.entryOrder) : num;
            }
        }
    }
}